﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;

namespace TextCompare
{
    class TextMatch
    {
        public TextMatch(ITextMatcher textMatcher)
        {
            this.textMatcher = textMatcher;
        }

        public double CorrectPercent
        {
            get
            {
                return minPath.Count == 0 ? 0 : Math.Ceiling(((double)max * 2 / (double)(this.textMatcher.SourceCount + this.textMatcher.TargetCount)) * 100);
                //return max;
            }
        }

        public IEnumerable<MatchPoint> Match()
        {
            match = new int[textMatcher.SourceCount][];
            for (int i = 0; i < textMatcher.SourceCount; i++)
                match[i] = new int[textMatcher.TargetCount];

            matchPoint = new int[textMatcher.SourceCount + 1][];
            for (int i = 0; i < textMatcher.SourceCount + 1; i++)
                matchPoint[i] = new int[textMatcher.TargetCount + 1];

            CompletePath(CalculatePath(CalculateMatchPoint()));
            return minPath;
        }

        #region CalculateMatchPath

        private List<MatchPoint> CalculateMatchPoint()
        {
            System.Diagnostics.Stopwatch sw;
            sw = System.Diagnostics.Stopwatch.StartNew();

            List<MatchPoint> maxPoints = new List<MatchPoint>();
            max = 1;

            for (int i = textMatcher.SourceCount - 1; i >= 0; i--)
            {
                for (int j = textMatcher.TargetCount - 1; j >= 0; j--)
                {
                    if (textMatcher.Compare(i,j))
                    {
                        match[i][j] = 1;
                        matchPoint[i][j] = GetMax(matchPoint[i + 1][j], matchPoint[i + 1][j + 1] + match[i][j], matchPoint[i][j + 1]);

                        //Find the max point.
                        if (matchPoint[i][j] > max)
                        {
                            max = matchPoint[i][j];
                            maxPoints.Clear();
                            maxPoints.Add(new MatchPoint(i, j));
                        }
                        else if (matchPoint[i][j] == max)
                        {
                            maxPoints.Add(new MatchPoint(i, j));
                        }
                    }
                    else
                    {
                        match[i][j] = 0;
                        matchPoint[i][j] = GetMax(matchPoint[i + 1][j], matchPoint[i + 1][j + 1] + match[i][j], matchPoint[i][j + 1]);
                    }
                }
            }
            //MessageBox.Show(sw.Elapsed.ToString());

            return maxPoints;
        }

        // Find the shortest path
        private Point CalculatePath(List<MatchPoint> maxPoints)
        {
            minPath = new List<MatchPoint>();
            Point startPoint = new Point();

            if (maxPoints.Count != 0)
            {
                minPath = GeneratePath(maxPoints[0]);
                startPoint.X = maxPoints[0].X;
                startPoint.Y = maxPoints[0].Y;

                //for (int i = 1; i < maxPoints.Count; i++)
                //{
                //    var path = GeneratePath(maxPoints[i]);
                //    if (minPath.Count > path.Count)
                //    {
                //        minPath = path;
                //        startPoint.X = maxPoints[i].X;
                //        startPoint.Y = maxPoints[i].Y;
                //    }
                //}
            }
            return startPoint;
        }

        private List<MatchPoint> GeneratePath(MatchPoint point)
        {
            List<MatchPoint> path = new List<MatchPoint>();
            int i = point.X;
            int j = point.Y;
            Direction state = Direction.None;

            while (i <= textMatcher.SourceCount - 1 && j <= textMatcher.TargetCount - 1)
            {
                if (match[i][j] == 1)
                {
                    // correct
                    state = HandleState(path, i, state, Direction.DownRight);
                    i++;
                    j++;
                }
                else
                {
                    // delete
                    if (j + 1 < textMatcher.TargetCount && matchPoint[i][j] == matchPoint[i][j + 1])
                    {
                        state = HandleState(path, j, state, Direction.Right);
                        j++;
                        continue;
                    }

                    // insert
                    if (i + 1 < textMatcher.SourceCount && matchPoint[i][j] == matchPoint[i + 1][j])
                    {
                        state = HandleState(path, i, state, Direction.Down);
                        i++;
                        continue;
                    }

                    if (i + 1 == textMatcher.SourceCount && j + 1 == textMatcher.TargetCount)
                    {
                        state = HandleState(path, j, state, Direction.Right);
                        state = HandleState(path, i, state, Direction.Down);
                        i++;
                        j++;
                        continue;
                    }
                }
            }

            // complete
            if (state == Direction.DownRight)
            {
                if (i == textMatcher.SourceCount && j < textMatcher.TargetCount)
                {
                    path.Add(new MatchPoint(j, textMatcher.TargetCount - 1, Direction.Right));
                }
                else if (i < textMatcher.SourceCount && j == textMatcher.TargetCount)
                {
                    path.Add(new MatchPoint(i, textMatcher.SourceCount - 1, Direction.Down));
                }
            }

            return path;
        }

        private void CompletePath(Point point)
        {
            if (minPath.Count == 0)
                return;

            #region add path before first node
            if (point.X == 0 && point.Y != 0)
            {
                minPath.Insert(0, new MatchPoint(0, (int)point.Y - 1, Direction.Right));
            }
            else if (point.X != 0 && point.Y == 0)
            {
                minPath.Insert(0, new MatchPoint(0, (int)point.X - 1, Direction.Down));
            }
            else if (point.X != 0 && point.Y != 0)
            {
                minPath.Insert(0, new MatchPoint(0, (int)point.Y - 1, Direction.Right));
                minPath.Insert(1, new MatchPoint(0, (int)point.X - 1, Direction.Down));
            }
            #endregion
        }

        private Direction HandleState(List<MatchPoint> path, int position, Direction state, Direction direction)
        {
            if (state == direction)
            {
                path.Last().Y = position;
            }
            else
            {
                state = direction;
                path.Add(new MatchPoint(position, position, direction));
            }

            return state;
        }

        private int GetMax(int A, int B, int C)
        {
            int max = Math.Max(A, B);
            return Math.Max(max, C);
        }

        #endregion

        #region Fields

        private int max;
        private int[][] match;
        private int[][] matchPoint;
        private List<MatchPoint> minPath;
        private ITextMatcher textMatcher;

        #endregion
    }
}
